package io.github.maojian.demo;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 请勿改变本Java类的包名，类名，方法名，方法参数类型，方法返回值类型
 */

public class ProjectTasks {

    List<ListNode> list = new ArrayList<>();

    /**
     * 根据参数判断项目是否可以顺利完成，本方法按照竞赛题目要求完成
     *
     * @param tasks
     *            项目分解的任务数量
     * @param prerequisites
     *            任务的先决条件关系数组（二维数组）
     * @return 项目是否可以顺利完成，可以返回1，不可以返回0
     */
    public int isCanBeFinished(int tasks, int[][] prerequisites) {

        /*
         * 将任务先后关系维护为单向链表，如果链表有环则任务不能顺利完成
         */
        int length = prerequisites.length;
        for (int i = 0; i < length; i++) {
            int[] curTaskNode = prerequisites[i];
            int firstVal = curTaskNode[0];
            ListNode firstNode = addFirst(firstVal);
            int secondVal = curTaskNode[1];
            ListNode secondNode = new ListNode(secondVal);
            firstNode.next = secondNode;
        }

        for (ListNode node : list) {
            if (isHasLoop(node)) {
                return 0;
            }
        }
        return 1;
    }

    public boolean isHasLoop(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode temp = head;
        while (temp != null) {
            if (set.contains(temp)) {
                return true;
            } else {
                set.add(temp);
                temp = temp.next;
            }
        }
        return true;
    }

    public ListNode addFirst(int val) {
        ListNode curNode = null;
        for (ListNode head : list) {
            if (isExist(head, val)) {
                curNode = getNodeByVal(head, val);
            }
        }
        if (curNode == null) {
            curNode = new ListNode(val);
            list.add(curNode);
        }
        return curNode;
    }

    /**
     * 判断是节点否存在
     * @param head
     * @param val
     * @return
     */
    private boolean isExist(ListNode head, int val) {
        ListNode temp = head;
        while (temp != null) {
            if (val == head.getVal()) {
                return true;
            } else {
                temp = temp.next;
            }
        }
        return false;
    }

    /**
     * 根据 val查找node
     * @param head
     * @param val
     * @return
     */
    private ListNode getNodeByVal(ListNode head, int val) {
        ListNode temp = head;
        while (temp != null) {
            if (temp.getVal() == val) {
                return temp;
            } else {
                temp = temp.next;
            }
        }
        return head;
    }

    public static void main(String[] args) {
        ProjectTasks func = new ProjectTasks();
        int ret = func.isCanBeFinished(2, new int[][]{{0, 1}});
        System.out.println(ret);
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }
    }

}
